home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr47 / lz13.zip / LZCOMP1.ASM < prev    next >
Assembly Source File  |  1993-05-01  |  7KB  |  299 lines
  1.     title    lzcomp - file compressor using limpel-ziv algorithm
  2.  
  3. ;Tom Pfau
  4. ;Digital Equipment Corporation
  5. ;Parsippany, NJ
  6.  
  7. ;Constants
  8. CLEAR        equ    256        ;Clear code
  9. EOF        equ    257        ;End of file marker
  10. FIRST_FREE    equ    258        ;First free code
  11. MAXMAX        equ    4096        ;Max code + 1
  12.  
  13.     include macros1.mlb
  14.  
  15. ;Hash table entry
  16. hash_rec    struc
  17. first    dw    ?            ; First entry with this value
  18. next    dw    ?            ; Next entry along chain
  19. char    db    ?            ; Suffix char
  20. hash_rec    ends
  21.  
  22. ;Declare Segments
  23. code    segment byte public 'code'
  24. code    ends
  25. stack    segment word stack 'data'
  26.     dw    128 dup (?)
  27. stack    ends
  28.  
  29. data    segment word public 'data'
  30. data    ends
  31.  
  32. memory    segment para public 'memory'
  33. hash    label    hash_rec
  34. memory    ends
  35.  
  36. ;Start writing code
  37. code    segment
  38.     assume    CS:code,DS:data,ES:data,SS:stack
  39.  
  40. start    proc    far
  41.     mov    bx,seg hash        ;End of program
  42.     mov    ax,DS            ;Start of program
  43.     sub    bx,ax            ;Program size
  44.     inc    bx            ;Make sure
  45.     setmem    bx            ;Set our size
  46.     mov    bx,data            ;Set up data segment addressability
  47.     mov    ES,bx
  48.     mov    DS,bx
  49.     print    input_prompt        ;Get input file name
  50.     input    input_file
  51.     print    crlf
  52.     print    output_prompt        ;And output
  53.     input    output_file
  54.     print    crlf
  55.     mov    al,input_file+1        ;Terminate file names with nulls
  56.     xor    ah,ah
  57.     mov    si,ax
  58.     mov    input_file+2[si],0
  59.     mov    al,output_file+1
  60.     mov    si,ax
  61.     mov    output_file+2[si],0
  62.     hopen    input_file+2,0
  63.     mov    input_handle,ax
  64.     hcreat    output_file+2,0
  65.     mov    output_handle,ax
  66.     call    compress        ;Compress file
  67.     hclose    input_handle        ;Close in and out
  68.     hclose    output_handle
  69.     exit                ;Done
  70. start    endp
  71.  
  72. data    segment
  73. input_prompt    db    'Input file: $'
  74. output_prompt    db    'Output file: $'
  75. input_file    db    80,0,80 dup (?)
  76. output_file    db    80,0,80 dup (?)
  77. crlf        db    13,10,'$'
  78. input_handle    dw    ?
  79. output_handle    dw    ?
  80. data    ends
  81.  
  82. compress    proc    near
  83.     malloc    1280            ;Allocate space for hash table
  84.     mov    hash_seg,ax        ;Save segment address
  85. l1:    call    init_table        ;Initialize the table and some vars
  86.     mov    ax,CLEAR        ;Write a clear code
  87.     call    write_code
  88.     call    read_char        ;Read first char
  89. l4:    xor    ah,ah            ;Turn char into code
  90. l4a:    mov    prefix_code,ax        ;Set prefix code
  91.     call    read_char        ;Read next char
  92.     jc    l17            ;Carry means EOF
  93.     mov    k,al            ;Save char in k
  94.     mov    bx,prefix_code        ;Get prefix code
  95.     call    lookup_code        ;See if this pair in table
  96.     jnc    l4a            ;nc means yes, new code in ax
  97.     call    add_code        ;Add pair to table
  98.     push    bx            ;Save new code
  99.     mov    ax,prefix_code        ;Write old prefix code
  100.     call    write_code
  101.     pop    bx
  102.     mov    al,k            ;Get last char
  103.     cmp    bx,max_code        ;Exceed code size?
  104.     jl    l4            ;less means no
  105.     cmp    nbits,12        ;Currently less than 12 bits?
  106.     jl    l14            ;yes
  107.      mov    ax,CLEAR        ;Write a clear code
  108.      call    write_code
  109.      call    init_table        ;Reinit table
  110.      mov    al,k            ;get last char
  111.      jmp    l4            ;Start over
  112.  
  113. l14:    inc    nbits            ;Increase number of bits
  114.     shl    max_code,1        ;Double max code size
  115.     jmp    l4            ;Get next char
  116.  
  117. l17:    mov    ax,prefix_code        ;Write last code
  118.     call    write_code
  119.     mov    ax,EOF            ;Write EOF code
  120.     call    write_code
  121.     mov    ax,bit_offset        ;Make sure buffer is flushed to file
  122.     or    ax,ax    ;cmp    ax,0
  123.     je    l18
  124.     mov    cx,8            ;convert bits to bytes
  125.     xor    dx,dx
  126.     div    cx
  127.     or    dx,dx            ;If extra bits, make sure they get
  128.     je    l17a            ;written
  129.      inc    ax
  130. l17a:    call    flush
  131. l18:    ret
  132. compress    endp
  133.  
  134. data    segment
  135. hash_seg    dw    ?
  136. prefix_code    dw    ?
  137. free_code    dw    ?
  138. max_code    dw    ?
  139. nbits        dw    ?
  140. k        db    ?
  141. data    ends
  142.  
  143. init_table    proc    near
  144.     mov    nbits,9            ;Set code size to 9
  145.     mov    max_code,512        ;Set max code to 512
  146.     push    ES            ;Save seg reg
  147.     mov    ES,hash_seg        ;Address hash table
  148.     mov    ax,-1            ;Unused flag
  149.     mov    cx,640            ;Clear first 256 entries
  150.     mov    di,offset hash        ;Point to first entry
  151. rep    stosw                ;Clear it out
  152.     pop    ES            ;Restore seg reg
  153.     mov    free_code,FIRST_FREE    ;Set next code to use
  154.     ret                ;done
  155. init_table    endp
  156.  
  157. write_code    proc    near
  158.     push    ax            ;Save code
  159.     mov    ax,bit_offset        ;Get bit offset
  160.     mov    cx,nbits        ;Adjust bit offset by code size
  161.     add    bit_offset,cx
  162.     mov    cx,8            ;Convert bit offset to byte offset
  163.     xor    dx,dx
  164.     div    cx
  165.     cmp    ax,1020            ;Approaching end of buffer?
  166.     jl    wc1            ;less means no
  167.     call    flush            ;Write the buffer
  168.     push    dx            ;dx contains offset within byte
  169.     add    dx,nbits        ;adjust by code size
  170.     mov    bit_offset,dx        ;new bit offset
  171.     pop    dx            ;restore dx
  172.     add    ax,offset output_data    ;Point to last byte
  173.     mov    si,ax            ;put in si
  174.     mov    al,byte ptr [si]    ;move byte to first position
  175.     mov    output_data,al
  176.     xor    ax,ax            ;Byte offset of zero
  177. wc1:    add    ax,offset output_data    ;Point into buffer
  178.     mov    di,ax            ;Destination
  179.     pop    ax            ;Restore code
  180.     mov    cx,dx            ;offset within byte
  181.     xor    dx,dx            ;dx will catch bits rotated out
  182.     jcxz    wc3            ;If offset in byte is zero, skip shift
  183. wc2:     shl    ax,1            ;Rotate code
  184.      rcl    dx,1
  185.      loop    wc2
  186.      or    al,byte ptr [di]    ;Grab bits currently in buffer
  187. wc3:    stosw                ;Save data
  188.     mov    al,dl            ;Grab extra bits
  189.     stosb                ;and save
  190.     ret
  191. write_code    endp
  192.  
  193. data    segment
  194. bit_offset    dw    ?
  195. output_data    db    1024 dup (?)
  196. data    ends
  197.  
  198. flush        proc    near
  199.     push    ax            ;Save all registers
  200.     push    bx            ;AX contains number of bytes to write
  201.     push    cx
  202.     push    dx
  203.     hwrite    output_handle,output_data,ax    ;write output file
  204.     pop    dx
  205.     pop    cx
  206.     pop    bx
  207.     pop    ax
  208.     ret
  209. flush        endp
  210.  
  211. read_char    proc    near
  212.     mov    di,input_offset        ;Anything left in buffer?
  213.     cmp    di,input_size
  214.     jl    rd1            ;less means yes
  215.     hread    input_handle,input_data,1024    ;Read next chunk of input
  216.     or    ax,ax    ;TH cmp    ax,0    ;Anything left?
  217.     je    rd2            ;equal means no, finished
  218.  
  219.     mov    input_size,ax        ;Save bytes read
  220. ;    mov    input_offset,0        ;Point to beginning of buffer
  221.     xor    di,di    ;TH mov    di,0
  222.     mov    input_offset,di    ;TH 0    ;Point to beginning of buffer
  223. rd1:    lea    si,input_data[di]    ;Point at character
  224.     lodsb                ;Read it in
  225.     inc    input_offset        ;Adjust pointer
  226.     clc                ;Success
  227.     ret
  228.  
  229. rd2:    stc                ;Nothing left
  230.     ret
  231. read_char    endp
  232.  
  233. data    segment
  234. input_data    db    1024 dup (?)
  235. input_offset    dw    0
  236. input_size    dw    0
  237. data    ends
  238.  
  239. lookup_code    proc    near
  240.     push    DS            ;Save seg reg
  241.     mov    DS,hash_seg        ;point to hash table
  242.     call    index            ;convert code to address
  243.     xor    di,di    ;TH         ;flag
  244.     cmp    [si].first,-1        ;Has this code been used?
  245.     je    gc4            ;equal means no
  246.  
  247.     inc    di            ;set flag
  248.     mov    bx,[si].first        ;Get first entry
  249. gc2:    call    index            ;convert code to address
  250.     cmp    [si].char,al        ;is char the same?
  251.     jne    gc3            ;ne means no
  252.      clc                ;success
  253.      mov    ax,bx            ;put found code in ax
  254.      pop    DS            ;restore seg reg
  255.      ret                ;done
  256.  
  257. gc3:    cmp    [si].next,-1        ;More left with this prefix?
  258.     je    gc4            ;equal means no
  259.      mov    bx,[si].next        ;get next code
  260.      jmp    gc2            ;try again
  261.  
  262. gc4:    stc                ;not found
  263.     pop    DS            ;restore seg reg
  264.     ret                ;done
  265. lookup_code    endp
  266.  
  267. index        proc    near
  268.     mov    si,bx            ;si = bx * 5 (5 byte hash entries)
  269.     shl    si,1            ;si = bx * 2 * 2 + bx
  270.     shl    si,1
  271.     add    si,bx
  272.     ret
  273. index        endp
  274.  
  275. add_code    proc    near
  276.     mov    bx,free_code        ;Get code to use
  277.     push    DS            ;point to hash table
  278.     mov    DS,hash_seg
  279.     or    di,di    ;TH        ;First use of this prefix?
  280.     je    ac1            ;equal means yes
  281.      mov    [si].next,bx        ;point last use to new entry
  282.      jmp    short ac2
  283.  
  284. ac1:    mov    [si].first,bx        ;Point first use to new entry
  285. ac2:    cmp    bx,MAXMAX        ;Have we reached code limit?
  286.     je    ac3            ;equal means yes, just return
  287.      call    index            ;get address of new entry
  288.      mov    [si].first,-1        ;initialize pointers
  289.      mov    [si].next,-1
  290.      mov    [si].char,al        ;save suffix char
  291.      inc    ES:free_code        ;adjust next code
  292. ac3:    pop    DS            ;restore seg reg
  293.     ret
  294. add_code    endp
  295.  
  296. code    ends
  297.  
  298.     end    start
  299.